package com.example.find;

/**
 * 二分查找
 */
public class TwoFind {

    public static void main(String[] args) {
        int[] arr = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int middle = recursionBinarySearch(arr, 1, 0, arr.length - 1);
        System.out.println(middle);
    }

    /**
     * 递归实现
     * @param arr
     * @param target
     * @param low
     * @param high
     * @return
     */
    public static int recursionBinarySearch(int[] arr, int target, int low, int high) {
        if (target < arr[low] || target > arr[high] || low > high) {
            return -1;
        }

        int middle = (low + high) / 2;
        if (arr[middle] > target) {
            return recursionBinarySearch(arr, target, low, middle - 1);
        } else if (arr[middle] < target) {
            return recursionBinarySearch(arr, target, middle + 1, high);
        } else {
            return middle;
        }
    }

    public static int commonBinarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;

        if (target < arr[low] || target > arr[high] || low > high) {
            return -1;
        }

        while (low <= high) {
            middle = (low + high) / 2;
            if (arr[middle] > target) {
                high = middle - 1;
            } else if (arr[middle] < target) {
                low = middle + 1;
            } else {
                return middle;
            }
        }

        return -1;
    }
}
